Code-division multiple access (CDMA) communication systems are well known. One exemplary CDMA communication system is the so-called IS-95 which is defined for use in North America by the Telecommunications Industry Association (TIA). For more information on IS-95, see TIA/EIA/IS-95, Mobile Station-Base-station Compatibility Standard for Dual Mode Wideband Spread Spectrum Cellular System, January 1997, published by the Electronic Industries Association (EIA), 2001 Eye Street, N.W., Washington, D.C. 20006. A variable rate speech codec, and specifically Code Excited Linear Prediction (CELP) codec, for use in communication systems compatible with IS-95 is defined in the document known as IS-127 and titled Enhanced Variable Rate Codec, Speech Service Option 3 for Wideband Spread Spectrum Digital Systems, September 1996. IS-127 is also published by the Electronic Industries Association (EIA), 2001 Eye Street, N.W., Washington, D.C. 20006.
In the IS-127 Rate 1 case (8.5 kbps), the fixed codebook (FCB) uses a multipulse configuration (known as Algebraic Code Excited Linear Prediction or ACELP) in which the excitation vector c.sub.k contains only eight non-zero, unit magnitude values, or "pulses". For the eight pulses, there are 35 bits allocated for the pulse positions and associated signs for each of the three subframes (of length L=[53, 53, 54]). An associated "track" defines the allowable positions for each of the eight pulses within c.sub.k as defined in IS-127. In this configuration, three of the tracks contain two pulses and two tracks contain only one pulse. As shown in Table 1 (from Table 4.5.7.1-1 of IS-127), the pulse(s) on track 0 can occupy positions 0, 5, 10, . . . , 50, pulse(s) on track 2 can occupy positions 1, 6, 11, . . . , 51, and so on. This is known as "interleaved pulse permutation." The positions of the eight pulses are then chosen in a manner such that equation (12), recited below, is maximized in a reasonable number of iterations.
TABLE 1 IS-127 Rate 1 Pulse Positions Definitions Track Positions T0 0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50 T1 1, 6, 11, 16, 21, 26, 31, 36, 41, 46, 51 T2 2, 7, 12, 17, 22, 27, 32, 37, 42, 47, 52 T3 3, 8, 13, 18, 23, 28, 33, 38, 43, 48, 53 T4 4, 9, 14, 19, 24, 29, 34, 39, 44, 49, 54
In an effort to improve upon the IS-127 codebook design for higher bit rates, a design requirement may be to have twelve total pulses with three pulses on each of four separate tracks, with subframe sizes of L=[53, 53, 54], and a bit allocation of 48 bits per subframe. The advantage of having multiple pulses on a given track is (at least) twofold. First, multiple pulse tracks tend to be longer because there are fewer of them. This promulgates greater flexibility in pulse positioning; i.e., shorter track lengths limit flexibility and can potentially force pulses into suboptimal positions, resulting in decreased performance. Secondly, multiple pulses can "degenerate" into fewer pulses, i.e., pulses can occupy the same positions and become additive. This tends to refine the shape of the excitation sequence and hence, be a closer match to the target signal by providing limited amplitude information, as a byproduct of positioning information. Here, some of the benefits of the traditional multipulse (amplitude and position) are preserved. For additional information, see the article by I. M. Transcoso and B. S. Atal titled "Efficient Procedures for Finding the Optimum Innovation in Stochastic Coders" in the Proc. Int. Conf. Acoust., Speech, Signal Processing, 1987 at pages 1957-1960.
In the given scenario, the tracks would be configured as 4 tracks.times.14 positions=56 total positions, which could be positioned according to Table 2. Here, the bit allocation of 48 bits would be divided between the 4 tracks equally so that each track would receive 12 bits. The 12 bits per track would further be composed of 3 bits for each position and 1 sign bit to indicate the polarity of the each pulse. The problem is that only 8 positions can be represented by 3 bits (2.sup.3 =8). Coding the positions using 4+1=5 bits per pulse would require 60 bits per subframe, so that it is obvious that the requirement cannot be met in such a straightforward manner.
TABLE 2 Required Pulse Position Definitions Track Positions T0 0, 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52 T1 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53 T2 2, 6, 10, 14, 18, 22, 26, 30, 34, 38, 42, 46, 50, 54 T3 3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55
A method for pulse coding that is known in the prior art deals with multiplexing the indices of two pulses into a single codeword. For example, in the IS-127 Rate 1 case (8.5 kbps), there are 11 possible pulse positions spread over five tracks. Rather than using four bits for each pulse position, the positions of two pulses can be coded jointly using only seven bits. This is accomplished by considering that the total number of positions for two pulses is 11.times.11=121, which is less than the total number of positions that can be coded with seven bits (2.sup.7 =128). Details of the coding can then be expressed as: ##EQU1##
where p.sub.i and p.sub.j are the positions of the i-th and j-th pulses, N.sub.pos is the number of pulse positions per track, N.sub.track is the number of tracks, and .left brkt-bot.x.right brkt-bot. represents the largest integer less than or equal to x. The pulse positions can then be extracted at the decoder by: ##EQU2##
where .lambda..sub.i and .lambda..sub.j are the decimated positions within the appropriate track, which corresponds to the columns in Table 2 (i.e., p.sub.i =N.sub.t.lambda..sub.i +n where N.sub.t is the number of tracks, and n is the track number). The problem with using this method for the 14 position, 3 pulse track case in Table 2, is that a 14.times.14.times.14=2,744 position multiplex would still require 12 bits (2.sup.12 =4096 possible positions), so there is no savings over simply using four bits for each pulse position.
In the case of multiple pulse tracks, however, there is a built-in redundancy that has been exploited in the prior art. Again in IS-127, the two pulse track positions are indistinct, i.e., the first pulse can be interchanged with the second pulse with no change in outcome. Therefore, efficient sign coding has been embedded in the position information: if the signs of the two pulses are the same, the packing order is such that the pulses are ascending in position (i.e., the position of the first pulse is less than or equal to the position of the second pulse, or p.sub.i.ltoreq.p.sub.j). Otherwise, the positions are descending (the position of the first pulse is greater than the position of the second pulse, or p.sub.i &gt;p.sub.j). This allows the tracks to be coded using only 7 bits plus 1 sign bit (instead of 2) for a total of 8 bits for an 11 position double pulse track.
In a triple pulse track, however, the complexity of this problem grows at a factorial rate. Rather than having 2!=2 permutations of indistinct pulses as described above, there are 3!=6 permutations, as shown in Table 3. In addition, there are 4 combinations of pulse degeneracy, in which two or more pulses occupy the same positions, also shown in Table 3.
TABLE 3 Redundancies in Triple Pulse Coding Indistinct Pulse Degenerative Pulse Combinations Combinations p.sub.i .ltoreq. p.sub.j .ltoreq. p.sub.k p.sub.i = p.sub.j .noteq. p.sub.k p.sub.i .ltoreq. p.sub.k .ltoreq. p.sub.j p.sub.i .noteq. p.sub.j = p.sub.k p.sub.j .ltoreq. p.sub.i .ltoreq. p.sub.k p.sub.i = p.sub.k .noteq. p.sub.j p.sub.k .ltoreq. p.sub.j .ltoreq. p.sub.i p.sub.i = p.sub.j = p.sub.k p.sub.j .ltoreq. p.sub.k .ltoreq. p.sub.i p.sub.k .ltoreq. p.sub.i .ltoreq. p.sub.j
One problem with the prior art in this case is that the number of indistinct pulse combinations (3!=6) exceeds the total number of sign change combinations (2.sup.(3-1) =4 required to embed the sign information with the position information. This results in a coding inefficiency since only two thirds (4/6) of the position information is required to embed the sign change information, thus one third of the total coded representations will be redundant. This problem is further exemplified in Table 4, which shows how the coding inefficiencies in the prior art grow as the number of pulses per track increases. Here, as the number of pulses per track m increases, the corresponding pulse sign combinations increase as 2.sup.m. Extending the information in Table 3, the number of position combinations that can be used to embed the sign information implicitly (according to the prior art) increases as m!. If this number is less than the number of required pulse sign combinations, then explicit sign bits (shown in column 3 of Table 4) are required to code all the information. Otherwise, no explicit sign bits are needed.
But as the number of pulses per track increases, the available coding space (m!) far exceeds the amount of information needed to be coded (2.sup.m), hence the coding efficiency (defined as E=2.sup.(m-s) /m!) becomes impractically low. The efficiency can also be thought of in terms of effective bit loss (-log.sub.2 (E)), which can be observed to be quite high.
TABLE 4 Inefficiencies in multiple pulse coding using the prior art Required Coding efficiency Number Required Available pulse number of (assuming 100% of pulses pulse sign sign combinations dedicated position efficiency, per track combinations from positioning sign bits e.g., 8, 16, 32 Effective bit (m) (2.sup.m) (m!) (s) positions) loss per track 2 4 2 1 100.00% 0.0 3 8 6 1 66.67% 0.6 4 16 24 0 66.67% 0.6 5 32 120 0 26.67% 1.9 6 64 720 0 8.89% 3.5 7 128 5040 0 2.54% 5.3 8 256 40320 0 0.63% 7.3 9 512 362880 0 0.14% 9.5 10 1024 3628800 0 0.03% 11.8
In addition, the degenerate pulse combinations further degrade coding efficiency as the number of pulses to be coded increases. This is due to the inherent property that all pulses at a given position will have the same sign (since pulses at the same position with opposite sign will cancel). Thus, there is no need to code the pulse sign information for degenerated pulses independently.
Returning to the original problem of coding 3 pulses on 14 positions using only 12 bits, and using the information in Table 4, we can apply the prior art position coding with 1 dedicated sign bit to yield a codeword length of 1+(3*4)=13 bits. This, however does not meet the requirement of 12 bits (or 48 bits per subframe). Furthermore, as more and more pulses are to be coded within a single track, the prior art becomes more and more inefficient. Thus, a need exists for an improved method and apparatus which overcomes the deficiencies of the prior art and allows efficient coding of multiple pulse position tracks.